647. 回文子串

Similar Question

Solution Tips

方案一: 中心扩展法

分别以奇数和偶数为中心

function countSubstrings(s: string): number {
    const length: number = s.length;
    let resCount: number = 0;
    for (let i = 0; i < length; i++) {
        resCount += expandRange(s, i, i);
        resCount += expandRange(s, i, i + 1);
    }
    return resCount;
};
function expandRange(s: string, left: number, right: number): number {
    let palindromeNum: number = 0;
    while (
        left >= 0 && right < s.length &&
        s[left] === s[right]
    ) {
        palindromeNum++;
        left--;
        right++;
    }
    return palindromeNum;
}

奇数、偶数二合一, 感觉不好理解

const countSubstrings = (s) => {
    const strLen = s.length;
    let numOfPalindromicStr = 0;

    for(let i = 0; i < 2 * strLen - 1; i++) {
        let left = Math.floor(i/2);
        let right = left + i % 2;

        while(left >= 0 && right < strLen && s[left] === s[right]){
            numOfPalindromicStr++;
            left--;
            right++;
        }
    }

    return numOfPalindromicStr;
}

方案二: 中心扩展法的动态规划表示

var countSubstrings = function(s) {
    // 关键就是如何拆解出子问题, 因为回文串不能只看一个方向的
    // 子串是回文串, 要在两头都加入相同的字符才能继续构成子串
    // 难道这就是中心扩展法?
    // dp[i][j] 表示以 i 为中心, 向两边扩展 j 个字符, 是否是回文串
    // 插入空位, 处理偶数 case
    s = s.split('').join(' ');
    const half = Math.floor(s.length / 2);
    const dp = Array.from({ length: half });
    // 所有的 dp[i][0] 都为 true , 因为单个字符一定是回文串
    // 如果要应付偶数的情况, 那还得从空位开始扩展才行, 如果总是从单个字符开始扩展就只能处理奇数个字符
    let res = 0;
    for (let i = 0; i < s.length; i++) {
        for (let j = 0; j <= half; j++) {
            // j > 0
            const l = i - j;
            const r = i + j;
            if (j === 0) {
                dp[j] = true;
            }
            else {
                // l和r都在索引范围内, 并且不同为空串
                if (l >= 0 && r < s.length) {
                    // 空间复杂度太高了, 只依赖一行的, 一个行就够了
                    dp[j] = dp[j - 1] && s[l] === s[r];
                }
                else {
                    dp[j] = false;
                }
            }
            if (dp[j] && s[l] !== ' ' && s[r] !== ' ') {
                // slice i+-j
                const sub = s.slice(i - j, i + j + 1);
                sub !== ' ' && res++
            }
        }
    }

    return res;
};